package SwordOffer;

import java.util.HashMap;
import java.util.Map;

public class Sword_Offer_07 {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) {
            return null;
        }
        // 记录中序遍历的值分别在数组中的位置
        Map<Integer, Integer> inMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inMap.put(inorder[i], i);
        }
        return getRoot(preorder, 0 , inMap, 0, inorder.length - 1);
    }

    private TreeNode getRoot(int[] preorder, int preBegin, Map<Integer, Integer> inMap, int inBegin, int inEnd) {
        int rootVal = preorder[preBegin];
        TreeNode root = new TreeNode(rootVal);

        Integer inRootValIndex = inMap.get(rootVal);
        int leftNum = inRootValIndex - inBegin;
        int rightNum = inEnd - inRootValIndex;
        if (leftNum > 0) {
            root.left = getRoot(preorder, preBegin + 1, inMap, inBegin, inRootValIndex - 1);
        }
        if (rightNum > 0) {
            root.right = getRoot(preorder, preBegin + leftNum + 1, inMap, inRootValIndex + 1, inEnd);
        }
        return root;
    }

    public static void main(String[] args) {
        Sword_Offer_07 model = new Sword_Offer_07();
        TreeNode node = model.buildTree(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7});
        System.out.println(node);
    }

    class TreeNode {

        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
